package com.zyk.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author zhangsan
 * @date 2021/4/21 14:38
 */
public class C32 {

    // 最长连续, 不是总共有多少对, 天天读错题意
    public static int longestValidParentheses(String s) {
        if(s == null || s.length() == 0) return 0;
        int ans = 0, N = s.length();
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);
        for (int i = 0; i < N; i++) {
            if(s.charAt(i) == '(') {
                stack.push(i);
            }else {
                stack.pop();            // 否则就取
                if(stack.isEmpty()) {
                    stack.push(i);          // 栈为空, 开始放入新的开始点
                }else {
                    ans = Math.max(ans, i - stack.peek());  // 每次都计算答案
                }
            }
        }
        return ans;
    }


    // for test
    public static void main(String[] args) {
        String s = "()(()";
        System.out.println(longestValidParentheses(s));
    }

}
